package LeetCodeHot100;

/**
 * 31. 下一个排列
 *     整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 *     思路：这道题不好做，要考虑当前排列的下一个排列，而且不允许使用额外空间。
            希望下一个数比前一个数要大，尽可能选择右边较小的大数，然后替换，替换后要考虑右边是否顺序还是逆序，如果是逆序，需要反转
 */
public class LeetCode31 {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int i = len - 2;
        int j = len - 1;
        int k = len - 1;
        // 从后往前找，第一个相对较小的数字
        while (i>= 0 && nums[i] >= nums[j]){
            i--;
            j--;
        }
        if(i>=0){ //不是最后一个序列
            //然后找尽可能是右边较小的大数
            while (nums[i]>=nums[k]){
                k--;
            }
            // 替换
            swap(nums,i,k);
        }
        //最后再将后面的逆序反转
        reverse(nums,j,len-1);
    }

    private void swap(int[] nums,int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    private void reverse(int[] nums,int a,int b){
        while (a<b){
            swap(nums,a++,b--);
        }
    }
}
